package com.cat.binaryTree;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/print-binary-tree/description/
 * @create 2025/9/30 21:05
 * @since JDK17
 */

public class Solution98 {
    List<List<String>> ans = new ArrayList<>();
    int height;
    int deep(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return Math.max(deep(root.left), deep(root.right)) + 1;
    }

    void dfs(TreeNode root, int r, int c) {
        if (root == null) {
            return;
        }
        ans.get(r).set(c, String.valueOf(root.val));
        dfs(root.left, r + 1, c - (1 << height - r - 1));
        dfs(root.right, r + 1, c + (1 << height - r - 1));
    }

    public List<List<String>> printTree(TreeNode root) {
        height = deep(root);
        for (int i = 0; i <= height; i++) {
            ArrayList<String> list = new ArrayList<>();
            for (int j = 0; j < (1 << height + 1) - 1; j++) {
                list.add("");
            }
            ans.add(list);
        }
        dfs(root, 0, (height - 1) >> 1);
        return ans;
    }
}
